5.1 Algoritmos de enrutamiento

Enrutamiento

Determinar buenas rutas desde los emisores hasta los receptores a través de la red de routers.

Dado un conjunto de routers, con enlaces que conectan dichos routers, un algoritmo de enrutamiento determina una “buena” ruta desde el router de origen al router de destino.
Normalmente, una buena ruta es aquella que tiene el coste mínimo.

Un algoritmo de enrutamiento global calcula la ruta de coste mínimo entre un origen y un destino utilizando el conocimiento global y completo acerca de la red.
En un algoritmo de enrutamiento descentralizado, el cálculo de la ruta de coste mínimo se realiza de manera iterativa y distribuida. Ningún nodo tiene toda la información acerca del coste de todos los enlaces de la red. En lugar de ello, al principio, cada nodo sólo conoce los costes de sus propios enlaces directamente conectados.
En los algoritmos de enrutamiento estático, las rutas cambian muy lentamente con el tiempo, con frecuencia como resultado de una intervención humana.
Los algoritmos de enrutamiento dinámico modifican los caminos de enrutamiento a medida que la carga de tráfico o la topología de la red cambian. Un algoritmo dinámico puede ejecutarse periódicamente o como respuesta directa a cambios en la topología o en el coste de los enlaces.
En un algoritmo sensible a la carga, los costes de enlace varían de forma dinámica para reflejar el nivel actual de congestión en el enlace subyacente. Si se asocia un coste alto con un enlace que actualmente esté congestionado.

5.1.1 Algoritmo de enrutamiento de estado de enlaces (LS)
5.1.2 Algoritmo de enrutamiento por vector de distancias (DV)

Comparación LS y DV

Complejidad del mensaje: LS requiere que cada nodo conozca el coste de cada enlace de la red. Además, cuando el coste del enlace cambia, el nuevo coste tiene que enviarse a todos los nodos. El algoritmo de vector de distancias (DV) requiere intercambios de mensajes entre los vecinos directamente conectados en cada iteración. Cuando los costos de los enlaces cambian, el algoritmo de vector de distancias propagara los resultados del coste del enlace que ha cambiado solo si el nuevo coste de enlace da lugar a una ruta de coste mínimo distinta para no de los nodos conectados a dicho enlace.
Velocidad de convergencia: la implementación del algoritmo de estados de enlaces es un algoritmo que requiera enviar mensajes. El algoritmo de vector de distancias puede converger lentamente y pueden aparecer bucles de enrutamiento mientras está convergiendo. Este algoritmo también sufre el problema de la cuenta hasta infinito.
Robustez: LS proporcionando un mayor grado de robustez. Con el algoritmo de vector de distancias, un nodo puede anunciar rutas de coste mínimo incorrectas a cualquiera o a todos los destinos. Con el algoritmo de vector de distancias, un cálculo de nodo incorrecto puede difundirse a través de la red.